#include <string>
#include <map>
using namespace std;
class Solution
{
public:
    // 先把所有子串放进map中，然后直接返回即可
    string sortSentence(string s)
    {
        int left = 0, right = 0;
        map<int, string> sentence;
        bool is_true = true;
        while ((right = s.find(' ', left)) != string::npos || is_true)
        {
            // cout << right << endl;
            // 依次取每个单词，然后放入map中
            if (right == string::npos)
                is_true = false;
            string tmp = s.substr(left, right - left);
            char rank = tmp.back();
            tmp.pop_back();
            sentence[rank] = tmp;
            left = right + 1;
        }
        string ans;
        for (auto &e : sentence)
            ans += e.second + ' ';
        ans.pop_back();
        return ans;
    }
};